# P4 Fragestellungen

## Tries vs. Trees

Ein hauptsächlicher Unterschied ist, dass bei Tries im Gegensatz zu herkömmlichen Suchbäumen nicht Daten in individuellen Knoten gespeichert ist, sondern in die Kanten enkodiert wird. So ergibt sich beispielsweise ein Wort aus einer Sequenz von Kanten. Ein anderer spannender Anwendungsfall sind zum Beispiel Huffman Trees.

## Implementierung

Für `getCharAt(String, int)` wird ein trivialer range check durchgeführt, um die Java Methode `(String).charAt(int)` zu wrappen.

Bei `loopupKey(InnerNode, Key)` wird rekursiv ermittelt, ob ein Pfad der den vollständigen Key repräsentiert existiert. Dabei wird eine Hilfsmethode `loopupKey(InnerNode, Key, int)` verwendet, welche einfach den Trie durchläuft und bei jedem Schritt einen `int` inkrementiert, bis dieser die Länge des `Key` erreicht. Ist anschließend dieser Prozedur tatsächlich ein Blattknoten vorhanden, so übergeben wir falls dieser den Schlüssel hält `true`.

Mehr Komplexität findet sich bei `insertKey(InnerNode, LeafNode, int)`, wo es einige edge cases zu beachten gibt. Die erste Annahme ist, dass die Wurzel nicht `null` ist. Das ist für den initiellen Aufruf gewährleistet und subsequent in der Suche auch, es sei denn, wir erreichen eine Stelle an welcher ein Element einzufügen wäre. Die Suche ist von gleicher Natur wie auch schon bei `lookupKey`, wo der Trie durchläuft wird. In jedem Schritt wird der nächste Buchstabe des Schlüssels verwendet um den Kindknoten des Wurzelknoten zu entnehmen. Jetzt gibt es zwei unterschiedliche Szenarien:

1. Kindknoten ist `null`
2. Kindknoten ist nicht `null`

Bei Szenario 1 sind wir bereits an eine Stelle gelangt an der wir nicht weiter suchen können. Wenn hier noch kein Kindknoten vorliegt, so können wir einen mit unserem einzufügenden Blattknoten erstellen. Aber um sicher gehen zu können, muss überprüft werden, ob nicht bereits Kindknoten vorhanden sind. Ist ein Kindknoten der ein Blattknoten ist vorhanden, so legen wir eine `InnerNode` an und versuchen subsequent an dieser Stelle unseren Blattknoten einzufügen. Findet sich kein Kindknoten, können wir unseren Blattknoten sorglos einfügen.

Bei Szenario 2 liegt auf dem Pfad den die Suche zu unserem einzufügenden Blattknoten nehmen müsste bereits ein Kindknoten vor. Ist dieser derselbe Blattknoten wie der, den wir versuchen einzufügen, so sind wir fertig, da Duplikate verworfen werden. Handelt es sich um einen anderen Blattknoten, so müssen wir diesen stattdessen an eine `InneNode` anhängen. Handelt es sich um ein `InnerNode`, so durchlaufen wir mithilfe eines rekursiven Aufrufs weiter den Trie.

## Performance, *shuffled*

![Benchmark, shuffled](./res/p4-1.png)

Es lässt sich nur schwer erkennen, aber Binary Tree und Trie befinden sich in derselben Größenordnung. Das ergibt Sinn, weil binäre Suchbäume bei einer angemessenen Annahme zufälliger Daten mit ihrer erwarteten durchschnittlichen Laufzeit nur logarithmische Komplexität aufweisen, da deren Höhe logarithmisch ist. Ähnliches kann auch für den Trie argumentiert werden. Schließlich wird wie bei einem Suchbaum bei einem Trie mithilfe mehrerer von einer Wurzel ausgehende Kanten der Suchraum eingeschränkt. Die lineare Liste weist unüberraschenderweise eine lineare Laufzeitkomplexität auf, wie auch zu erwarten wäre.

## Performance, *ordered*

![Benchmark, ordered](./res/p4-2.png)

Unser nächster Benchmark schaut schon wieder ganz anders aus. An dieser Stelle gilt die Annahme ausreichender Zufälligkeit nicht, da durch die Ordnung der Daten der binäre Suchbaum zu einer linearen Liste entartet. Wie sich erkennen lässt, performed der binäre Suchbaum sogar schlechter als die lineare Liste, was sich durch den zusätzlichen Overhead einer Suchbaumimplementierung erklären lässt. Der Trie hingegen weist keine Unterschiede zum vorhergehenden Experiment auf. Um einen Trie entarten zu lassen, müssten in einem Extremfall Wörter, die nur aus einem Buchstaben bestehen, eingefügt werden. In einem realistischen Szenario ist das unwahrscheinlich und im Durchschnitt werden sich die Daten auf jeder Ebene entsprechend aufteilen. Daher behalten wir bei einem Trie in diesem Fall dieselbe Laufzeitkomplexität.
